package Leetcode;

/**
 * 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
 * ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
 * 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
 * 你可以假设数组中不存在重复的元素。
 * 你的算法时间复杂度必须是 O(log n) 级别。
 * 示例 1:
 * 输入: nums = [4,5,6,7,0,1,2], target = 0
 * 输出: 4
 * 示例 2:
 * 输入: nums = [4,5,6,7,0,1,2], target = 3
 * 输出: -1
 *
 */
public class L33_搜索旋转排序数组 {
    /**
     * 将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
     * 此时有序部分用二分法查找。
     * 无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.
     */
    public boolean search(int[] nums, int target) {
        //下面那个是递归的，这个是非递归的，下面这个同时判断了是否重复
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            // 去重
            while (low < high && nums[low] == nums[low + 1]) {
                low++;
            }
            while (low < high && nums[high] == nums[high - 1]) {
                high--;
            }
            // 以下代码与题目33题一致，无修改地方
            int mid = (low + high) / 2;
            if (nums[mid] == target) {
                return true;
            }
            // 把数组大致分为两组，一组为左侧未旋转有序数组，一组为右侧旋转有序数组
            // 如[3 4 5 1 2]， [3，4，5]称为左侧，[1，2]称为右侧

            // 0~mid有序，向后规约条件
            // nums[mid] >= nums[0] 表示0~mid有序
            // target > nums[mid] 表示target位于左侧且大于nums[mid],向后规约
            // target < nums[0] 表示target位于右侧，向后规约
            if (nums[mid] >= nums[0] && (target > nums[mid] || target < nums[0])) {
                low = mid + 1;
            } else if (nums[mid] < nums[0] && target > nums[mid] && target < nums[0]) { // 0~mid无序(即包含翻转点)，向后规约条件
                // nums[mid] < nums[0] 表示nums[mid]位于右侧
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return false;
    }

    private int search_rec(int[] nums, int start, int end, int target){
        if(start > end){
            return -1;
        }
        int mid = (start + end) / 2;
        if(nums[mid] == target){
            return mid;
        }
        //这里很重要， 判断中间节点和最右边 是否有序，是的话，右边的继续二分
        //通过中间值和最右边的判断，就可以知道  右边有序不
        if(nums[mid] < nums[end]){
            //右边有序，继续二分
            if(nums[mid] < target && target <= nums[end]){//值在右边，缩小left为mid
                return search_rec(nums, mid+1, end, target);
            }else{
                return search_rec(nums, start, mid -1, target);
            }
        }else{//画图好理解
            //无需的，先看num跟当前mid的大小比对，如果比当前的小，二分查找左边，如果比当前大，就只能继续二分右边
            //不能 nums[mid] > target 这么判断，因为有可能值也跑到右边
            //一定要加上头尾 节点的判断！！！
            if(nums[start] <= target && target < nums[mid]){//判断是否跟左边的
                return search_rec(nums, start, mid -1, target);
            }else{
                //这里要画图
                return search_rec(nums, mid + 1, end, target);
            }
        }
    }

}
